import java.util.Arrays;
import java.util.Comparator;

import static java.lang.Integer.toBinaryString;

class Trie{
    class TrieNode{
        TrieNode[] mark;
        TrieNode(){
            mark=new TrieNode[2];
        }
    }

    TrieNode root;

    Trie(){
        root=new TrieNode();
    }

    static String numToBinString(int num){
        String partStr=Integer.toBinaryString(num);
        StringBuilder sb=new StringBuilder();
        while(sb.length()<30-partStr.length()){
            sb.append('0');
        }
        return sb.toString()+partStr;
    }

    int getMaxXor(int num){
        String strNum=numToBinString(num);
        TrieNode tmpNode=root;
        int result=0;
        for (int i = 0; i < strNum.length(); i++) {
            int tmpNum=strNum.charAt(i)-'0';
            int tarNum=(tmpNum+1)%2;
            if(tmpNode.mark[tarNum]!=null){
                result+=Math.pow(2,29-i);
                tmpNode=tmpNode.mark[tarNum];
            }
            else if(tmpNode.mark[tmpNum]!=null){
                tmpNode=tmpNode.mark[tmpNum];
            }
            else{
                break;
            }
        }
        return result;
    }

    void addTrieNode(int num){
        String strNum=numToBinString(num);
        TrieNode tmpNode=root;
        for (int i = 0; i < strNum.length(); i++) {
            int tmpNum=strNum.charAt(i)-'0';
            if(tmpNode.mark[tmpNum]==null){
                tmpNode.mark[tmpNum]=new TrieNode();
            }
            tmpNode=tmpNode.mark[tmpNum];
        }
    }
}

public class Solution1707 {
    public int[] maximizeXor(int[] nums, int[][] queries) {
        Arrays.sort(nums);
        int numQ = queries.length;
        int[][] newQueries = new int[numQ][3];
        for (int i = 0; i < numQ; ++i) {
            newQueries[i][0] = queries[i][0];
            newQueries[i][1] = queries[i][1];
            newQueries[i][2] = i;
        }
        Arrays.sort(newQueries, new Comparator<int[]>() {
            public int compare(int[] query1, int[] query2) {
                return query1[1] - query2[1];
            }
        });

        int[] ans = new int[numQ];
        Trie trie = new Trie();
        int idx = 0, n = nums.length;
        for (int[] query : newQueries) {
            int x = query[0], m = query[1], qid = query[2];
            while (idx < n && nums[idx] <= m) {
                trie.addTrieNode(nums[idx]);
                ++idx;
            }
            if (idx == 0) {
                ans[qid] = -1;
            } else {
                ans[qid] = trie.getMaxXor(x);
            }
        }
        return ans;
    }

}
